/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/range-sum-query-2d-mutable
   @Language: C++
   @Datetime: 19-05-08 10:38
   */

class NumMatrix {
	int rows, cols;
	vector<vector<int> > sums, matrix;
public:
	NumMatrix(vector<vector<int> > &matrix) {
		rows=matrix.size(), cols=matrix[0].size();
		this->matrix=matrix;
		sums=vector<vector<int> > (rows+1,vector<int>(cols+1,0));
		for(int i=0; i<rows; ++i){
			int sum=0;
			for(int j=0; j<cols; ++j){
				sum+=matrix[i][j];
				sums[i+1][j+1]=sums[i][j+1]+sum;
			}
		}
	}

	void update(int row, int col, int val) {
		const int diff=val-matrix[row][col];
		matrix[row][col]=val;
		for(int i=row; i<rows; ++i)
			for(int j=col; j<cols; ++j)
				sums[i+1][j+1]+=diff;
	}

	int sumRegion(int row1, int col1, int row2, int col2) {
		return sums[row2+1][col2+1]-sums[row1][col2+1]-sums[row2+1][col1]+sums[row1][col1];
	}
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * obj.update(row,col,val);
 * int param_2 = obj.sumRegion(row1,col1,row2,col2);
 */
